import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:二叉树
 * User: Admin
 * Date: 2022-05-21
 * Time: 18:49
 */
public class Main {

        public boolean backspaceCompare(String S, String T) {
            int i = S.length() - 1, j = T.length() - 1;
            int skipS = 0, skipT = 0;

            while (i >= 0 || j >= 0) {
                while (i >= 0) {
                    if (S.charAt(i) == '#') {
                        skipS++;
                        i--;
                    } else if (skipS > 0) {
                        skipS--;
                        i--;
                    } else {
                        break;
                    }
                }
                while (j >= 0) {
                    if (T.charAt(j) == '#') {
                        skipT++;
                        j--;
                    } else if (skipT > 0) {
                        skipT--;
                        j--;
                    } else {
                        break;
                    }
                }
                if (i >= 0 && j >= 0) {
                    if (S.charAt(i) != T.charAt(j)) {
                        return false;
                    }
                } else {
                    if (i >= 0 || j >= 0) {
                        return false;
                    }
                }
                i--;
                j--;
            }
            return true;
        }
    private boolean getPath(BinaryTree.TreeNode root, BinaryTree.TreeNode node, Stack<BinaryTree.TreeNode> stack) {
        if(root == null || node == null) return false;
        stack.push(root);
        if(root == node ) return true;

        boolean x = getPath(root.left,node,stack);
        if(x == true) {
            return true;
        }
        boolean y = getPath(root.right,node,stack);
        if(y == true) {
            return true;
        }
        stack.pop();
        return false;

    }

    public BinaryTree.TreeNode lowestCommonAncestor(BinaryTree.TreeNode root, BinaryTree.TreeNode p, BinaryTree.TreeNode q) {

        Stack<BinaryTree.TreeNode> stack1 = new Stack<>();
        getPath(root,p,stack1);

        Stack<BinaryTree.TreeNode> stack2 = new Stack<>();
        getPath(root,q,stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 < size2) {
            int size = size2 - size1;
            while(size > 0) {
                stack2.pop();
                size--;
            }
        } else {
            int size = size1 - size2;
            while(size > 0) {
                stack1.pop();
                size--;
            }
        }

        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }

    private BinaryTree.TreeNode prev = null;
    public void createTree(BinaryTree.TreeNode root) {
        if(root == null) return;

        createTree(root.left);
        root.left = prev;

        if(prev != null) {
            prev.right = root;
        }
        prev = root;
        createTree(root.right);

    }
    public BinaryTree.TreeNode Convert(BinaryTree.TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        createTree(pRootOfTree);

        BinaryTree.TreeNode node = pRootOfTree;

        while(node.left != null) {
            node = node.left;
        }
        return node;
    }

    int index = 0;
    public BinaryTree.TreeNode buildTreechild(int[] preorder, int[] inorder, int inbegin, int inend) {
        if(inbegin > inend) return null;

        BinaryTree.TreeNode root = new BinaryTree.TreeNode(preorder[index]);
        int indexOf = indexOrder(inorder,inbegin,inend,preorder[index]);
        index++;

        root.left = buildTreechild(preorder,inorder,inbegin,indexOf-1);
        root.right = buildTreechild(preorder,inorder,indexOf+1,inend);

        return root;
    }

    public int indexOrder(int[] inorder,int inbegin,int inend ,int val) {
        for(int i = inbegin; i <=inend;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    public BinaryTree.TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreechild(preorder,inorder,0,inorder.length-1);
    }
}
